package com.bo.day20231201;

import java.util.Arrays;

/**
 * 已知一个几乎有序的数组，几乎有序是指如果把数组排好序的话，每个元素移动的距离可以不超过K，并且K相对于数组来说比较小。
 *
 * @Author: gpb
 * @Date: 2023/12/5 15:15
 * @Description:
 */
public class SortArrayDistanceLessK {

    public static void main (String[] args) {
        System.out.println("test begin");
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int k = (int) (Math.random() * maxSize) + 1;
            int[] arr = randomArrayNoMoveMoreK(maxSize, maxValue, k);
            int[] arr1 = copyArray(arr);
            int[] arr2 = copyArray(arr);
            sortedArrDistanceLessK(arr1, k);
            comparator(arr2, k);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                System.out.println("K : " + k);
                printArray(arr);
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }

    public static void sortedArrDistanceLessK (int[] arr, int k) {
        if (k == 0) {
            return;
        }
        // 小根堆
        SmallHeap smallHeap = new SmallHeap(k + 1);
        int index = 0;
        // 创建小根堆
        for (; index <= Math.min(arr.length - 1, k - 1); index++) {
            smallHeap.push(arr[index]);
        }
        int i = 0;
        for (; index < arr.length; i++, index++) {
            smallHeap.push(arr[index]);
            arr[i] = smallHeap.pop();
        }
        while (!smallHeap.isEmpty()) {
            arr[i++] = smallHeap.pop();
        }
    }

    // for test
    public static void comparator (int[] arr, int k) {
        Arrays.sort(arr);
    }

    // for test
    public static int[] randomArrayNoMoveMoreK (int maxSize, int maxValue, int K) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        // 先排个序
        Arrays.sort(arr);
        // 然后开始随意交换，但是保证每个数距离不超过K
        // swap[i] == true, 表示i位置已经参与过交换
        // swap[i] == false, 表示i位置没有参与过交换
        boolean[] isSwap = new boolean[arr.length];
        for (int i = 0; i < arr.length; i++) {
            int j = Math.min(i + (int) (Math.random() * (K + 1)), arr.length - 1);
            if (!isSwap[i] && !isSwap[j]) {
                isSwap[i] = true;
                isSwap[j] = true;
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        return arr;
    }

    // for test
    public static int[] copyArray (int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual (int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray (int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }


    /**
     * 小根堆
     */
    public static class SmallHeap {
        private int heapSize = 0;
        private final int limit;
        private int[] heap;

        public SmallHeap (int limit) {
            this.heap = new int[limit];
            this.limit = limit;
        }

        public boolean isEmpty () {
            return heapSize == 0;
        }

        public boolean isFull () {
            return heapSize == limit;
        }

        public void push (int value) {
            if (isFull()) {
                throw new RuntimeException("heap is full");
            }
            heap[heapSize] = value;
            // heapInsert(heap, heapSize++);
            heapInsertRecursion(heap, heapSize++);
        }

        /**
         * 添加逻辑
         * 添加到数组最后一位,依次和父节点进行比较,如果比父节点大,和父节点交换
         *
         * @param heap  堆
         * @param index
         */
        private void heapInsert (int[] heap, int index) {
            while (heap[index] < heap[(index - 1) / 2]) {
                swap(heap, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void heapInsertRecursion (int[] heap, int index) {
            if (heap[index] > heap[(index - 1) / 2] || index == 0) {
                return;
            }
            swap(heap, index, (index - 1) / 2);
            index = (index - 1) / 2;
            heapInsertRecursion(heap, index);
        }

        public int pop () {
            int t = heap[0];
            swap(heap, 0, --heapSize);
            //heapify(heap, 0, heapSize);
            heapifyRecursion(heap, 0, heapSize);
            return t;
        }

        // 从index位置，往下看，不断的下沉
        // 停：较大的孩子都不再比index位置的数大；已经没孩子了
        private void heapify (int[] heap, int index, int heapSize) {
            // 左孩子
            int left = index * 2 + 1;
            // 如果有左孩子,有没有右孩子,有可能有没有
            while (left < heapSize) {
                // 找出最小孩子的下标,看看左孩子还是右孩子小
                // 如果 left+1 小于 heapSize 说明存在右孩子,存在就比较左孩子还是右孩子小
                int ans = (left + 1) < heapSize && heap[left + 1] < heap[left] ? left + 1 : left;
                // 如果当前位置小于最小孩子,说明不需要下沉了,大于最小孩子,继续下沉
                ans = heap[index] < heap[ans] ? index : ans;
                if (ans == index) {
                    break;
                }
                swap(heap, ans, index);
                index = ans;
                left = index * 2 + 1;
            }
        }

        // 从index位置，往下看，不断的下沉
        // 停：较大的孩子都不再比index位置的数大；已经没孩子了
        private void heapifyRecursion (int[] heap, int index, int heapSize) {
            // 左孩子
            int left = index * 2 + 1;
            if (left >= heapSize) {
                return;
            }
            // 找出最小孩子的下标,看看左孩子还是右孩子小
            // 如果 left+1 小于 heapSize 说明存在右孩子,存在就比较左孩子还是右孩子小
            int ans = (left + 1) < heapSize && heap[left + 1] < heap[left] ? left + 1 : left;
            // 如果当前位置小于最小孩子,说明不需要下沉了,大于最小孩子,继续下沉
            ans = heap[index] < heap[ans] ? index : ans;
            if (ans == index) {
                return;
            }
            swap(heap, ans, index);
            index = ans;
            heapifyRecursion(heap, index, heapSize);
        }

        /**
         * 数组位置交换
         */
        public static void swap (int[] arr, int l, int r) {
            int t = arr[l];
            arr[l] = arr[r];
            arr[r] = t;
        }
    }
}
